package com.sise.Tree;

/**
 *      题目：是否是一颗二叉搜索树？
 *
 *      1、终止条件：         判断节点为空，
 *      2、返回什么信息：      返回当前子树的是否为平衡树
 *      3、本次递归应该返回什么：当前节点与左右子树的数值大小判断
 */
public class IsValidBST {

    /**
     * 这里使用了三个参数，其中的 min、max 作为辅助参数一直往下传递，一开始设置为 null
     */
    boolean isValidBST(TreeNode root) {
        return isValidBST(root, null, null);
    }

    boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
        // 如果 root 为空，说明到底了，直接返回 true 即可
        if (root == null) return true;

        // 下面两个 if 语句的意思： min <= root <= max 才是对的，其余都是错的
        if (min != null && root.val <= min.val) return false;
        if (max != null && root.val >= max.val) return false;

        /**
         *  下面分为左节点、右节点两种情况。只有两种情况都满足的情况下才返回 true，
         *     1、左节点：向左节点走的话，意味着当前节点为 左子树中最大的数值，故此将 root 作为 max 的值一直传递下去。对于左子树而言，头节点的值肯定比左子树的值都要大，否则就不是平衡二叉树。
         *     2、右节点：向右节点走的话，意味着此时的 root 节点是右子树中最小的节点了。对于右子树而言，头节点的值肯定比右子树的值都要小，否则就不是平衡二叉树。
         *
         *  性质：
         *     1.左子树上所有结点的值均小于或等于它的根结点的值。 由此性质，故此确定 root.left、root(作为最大值) 两个节点的值，
         *     2.右子树上所有结点的值均大于或等于它的根结点的值。
         *     3.左、右子树也分别为二叉排序树。
         *
         *  min、max 是会随着层数向左向右而改变的。
         */

        return isValidBST(root.left, min, root) && isValidBST(root.right, root, max);
    }

}
